home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 February: Technology Seed / Mac Tech Seed Feb '97.toast / OpenDoc 1.2b2c1 / Implementation / Storage / Bento / CM / ListMgr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-13  |  18.8 KB  |  547 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        ListMgr.c
  3.  
  4.     Contains:    Container Manager Doubly Linked Lists Routines
  5.  
  6.     Written by:    Ira L. Ruben
  7.  
  8.     Owned by:    Ed Lai
  9.  
  10.     Copyright:    © 1991-1994 by Apple Computer, Inc., all rights reserved.
  11.  
  12.     Change History (most recent first):
  13.  
  14.          <2>     8/26/94    EL        #1181622 Ownership update.
  15.          <2>      2/3/94    EL        Bento File names are now eight chars or
  16.                                                     less.
  17.  
  18.     To Do:
  19. */
  20.  
  21. /*---------------------------------------------------------------------------*
  22.  |                                                                           |
  23.  |                             <<< ListMgr.c >>>                             |
  24.  |                                                                           |
  25.  |               Container Manager Doubly Linked Lists Routines              |
  26.  |                                                                           |
  27.  |                               Ira L. Ruben                                |
  28.  |                                 11/26/91                                  |
  29.  |                                                                           |
  30.  |                  Copyright Apple Computer, Inc. 1991-1994                 |
  31.  |                           All rights reserved.                            |
  32.  |                                                                           |
  33.  *---------------------------------------------------------------------------*
  34.  
  35.  This file contains all the generic doubly linked list routines.  The routines are the
  36.  low level generic doubly linked list manipulators which the higher level "glue" routines
  37.  use.
  38.  
  39.  All structs list cells that are to be maintained as doubly linked lists with this package
  40.  must be of the form:
  41.  
  42.                  struct {
  43.                     ListLinksPtr theLinks;
  44.                     ...
  45.                 }...;
  46.                 
  47.  In other words, a field (any name will do) of type ListLinksPtr MUST be the first field
  48.  of the struct.  The caller allocates all the struct list cells.  This package enters
  49.  them into a list based whose head and tail are pointed to by a header which takes the
  50.  following form:
  51.  
  52.                  struct {
  53.                     ListHdr theListHeader;
  54.                     ...
  55.                 }...;
  56.  
  57.  This is similar to the list entries themselves.  Here a ListHdr is the first field of
  58.  some structure.
  59.  
  60.  Being a generic package the links and the header have to be at a know place in otherwise
  61.  arbitrary structs.  Hence the position requirements.
  62. */
  63.  
  64.  
  65. #include <stddef.h>
  66. #include <stdio.h>
  67.  
  68. #ifndef __CMTYPES__
  69. #include "CMTypes.h"
  70. #endif
  71. #ifndef __CM_API_TYPES__
  72. #include "CMAPITyp.h"
  73. #endif
  74. #ifndef __LISTMGR__
  75. #include "ListMgr.h"
  76. #endif
  77. #ifndef __SESSIONDATA__
  78. #include "Session.h"          
  79. #endif
  80. #ifndef __HANDLERS__
  81. #include "Handlers.h"
  82. #endif
  83.  
  84.                                                                     CM_CFUNCTIONS
  85.  
  86. /* The following generates a segment directive for Mac only due to 32K Jump Table             */
  87. /* Limitations.  If you don't know what I'm talking about don't worry about it.  The        */
  88. /* default is not to generate the pragma.  Theoritically unknown pragmas in ANSI won't    */
  89. /* choke compilers that don't recognize them.  Besides why would they be looked at if        */
  90. /* it's being conditionally skipped over anyway?  I know, famous last words!                        */
  91.  
  92. #if CM_MPW
  93. #pragma segment ListMgr
  94. #endif
  95.  
  96.  
  97. /*-------------------------------------------------------------------*
  98.  | cmInitList - init a liast header with NULL head and tail pointers |
  99.  *-------------------------------------------------------------------*
  100.  
  101.  This routine takes a list header and initializes the head and tail pointers to NULL.  All
  102.  empty lists are assumed to have NULL head and tail pointers.  The function returns the
  103.  input header pointer as its result.
  104. */
  105.  
  106. void *cmInitList(const void *theList)
  107. {
  108.     ((ListHdrPtr)theList)->head = ((ListHdrPtr)theList)->tail = NULL;
  109.     ((ListHdrPtr)theList)->nbrOfCells = 0;
  110.     return ((void *)theList);
  111. }
  112.  
  113.  
  114. /*-----------------------------------------------------------------*
  115.  | cmInsertBeforeListCell - insert a list cell BEFORE another cell |
  116.  *-----------------------------------------------------------------*
  117.  
  118.  Given a pointer to a list header (theList), this routine inserts a new cell (theCell)
  119.  before another cell already on the list (beforeThisCell).  The function returns the
  120.  input inserted cell pointer as its result.
  121.  
  122.  If beforeThisCell is NULL this function inserts theCell at the beginning of the list.
  123.  
  124.  If theCell is NULL, nothing is done and NULL is returned.
  125. */
  126.  
  127. void *cmInsertBeforeListCell(const void *theList, const void *theCell, const void *beforeThisCell)
  128. {
  129.     if (theCell == NULL) return (NULL);                                                            /* safety                         */
  130.     
  131.     if (beforeThisCell == NULL) {                                                                        /* insert at beginning*/
  132.         ((ListLinksPtr)theCell)->prev = NULL;
  133.         ((ListLinksPtr)theCell)->next = ((ListHdrPtr)theList)->head;
  134.         
  135.         if (((ListHdrPtr)theList)->head)
  136.             ((ListHdrPtr)theList)->head->prev = (ListLinksPtr)theCell;
  137.         ((ListHdrPtr)theList)->head = (ListLinksPtr)theCell;
  138.         
  139.         if (((ListHdrPtr)theList)->tail == NULL)
  140.             ((ListHdrPtr)theList)->tail = (ListLinksPtr)theCell;
  141.     } else {                                                                                                                /* insert before             */
  142.         ((ListLinksPtr)theCell)->prev = ((ListLinksPtr)beforeThisCell)->prev;
  143.         ((ListLinksPtr)theCell)->next = (ListLinksPtr)beforeThisCell;
  144.         
  145.         if (((ListLinksPtr)beforeThisCell)->prev)
  146.             ((ListLinksPtr)beforeThisCell)->prev->next = (ListLinksPtr)theCell;
  147.         else                                                                                                                    /* new head                     */
  148.             ((ListHdrPtr)theList)->head = (ListLinksPtr)theCell;
  149.         
  150.         ((ListLinksPtr)beforeThisCell)->prev = (ListLinksPtr)theCell;
  151.     }
  152.     
  153.     ++((ListHdrPtr)theList)->nbrOfCells;                                                        /* count cell                    */
  154.     
  155.     return ((void *)theCell);
  156. }
  157.  
  158.  
  159. /*---------------------------------------------------------------*
  160.  | cmInsertAfterListCell - insert a list cell AFTER another cell |
  161.  *---------------------------------------------------------------*
  162.  
  163.  Given a pointer to a list header (theList), this routine inserts a new cell (theCell)
  164.  after another cell already on the list (beforeThisCell).  The function returns the
  165.  input inserted cell pointer as its result.
  166.  
  167.  If afterThisCell is NULL this function appends theCell to the end of the list.
  168.  
  169.  If theCell is NULL, nothing is done and NULL is returned.
  170. */
  171.  
  172. void *cmInsertAfterListCell(const void *theList, const void *theCell, const void *afterThisCell)
  173. {
  174.     if (theCell == NULL) return (NULL);                                                            /* safety                         */
  175.     
  176.     if (afterThisCell == NULL) {                                                                        /* append                            */
  177.         ((ListLinksPtr)theCell)->next = NULL;
  178.         ((ListLinksPtr)theCell)->prev = ((ListHdrPtr)theList)->tail;
  179.  
  180.         if (((ListHdrPtr)theList)->tail == NULL)
  181.             ((ListHdrPtr)theList)->head = (ListLinksPtr)theCell;
  182.         else
  183.             ((ListHdrPtr)theList)->tail->next = (ListLinksPtr)theCell;
  184.         ((ListHdrPtr)theList)->tail = (ListLinksPtr)theCell;
  185.     } else {                                                                                                                /* insert after                */
  186.         ((ListLinksPtr)theCell)->prev = (ListLinksPtr)afterThisCell;
  187.         ((ListLinksPtr)theCell)->next = ((ListLinksPtr)afterThisCell)->next;
  188.         
  189.         if (((ListLinksPtr)afterThisCell)->next)
  190.             ((ListLinksPtr)afterThisCell)->next->prev = (ListLinksPtr)theCell;
  191.         else                                                                                                                    /* new tail                     */
  192.             ((ListHdrPtr)theList)->tail = (ListLinksPtr)theCell;
  193.         
  194.         ((ListLinksPtr)afterThisCell)->next = (ListLinksPtr)theCell;
  195.     }
  196.     
  197.     ++((ListHdrPtr)theList)->nbrOfCells;                                                        /* count cell                    */
  198.     
  199.     return ((void *)theCell);
  200. }
  201.  
  202.  
  203. /*-------------------------------------------------------*
  204.  | cmAppendListCell - append a cell to the end of a list |
  205.  *-------------------------------------------------------*
  206.  
  207.  This function is the same as a cmInsertAfterListCell(theList, theCell, NULL), i.e., 
  208.  theCell is appended to the end of the list.  The function returns the input inserted
  209.  cell pointer as its result.
  210.  
  211.  If theCell is NULL, nothing is done and NULL is returned.
  212. */
  213.  
  214. void *cmAppendListCell(const void *theList, const void *theCell)
  215. {
  216.     if (theCell == NULL) return (NULL);                                                            /* safety                         */
  217.     
  218.     if (((ListHdrPtr)theList)->tail == NULL)
  219.         ((ListHdrPtr)theList)->head = (ListLinksPtr)theCell;
  220.     else
  221.         ((ListHdrPtr)theList)->tail->next = (ListLinksPtr)theCell;
  222.     ((ListLinksPtr)theCell)->prev = ((ListHdrPtr)theList)->tail;
  223.     
  224.     ((ListLinksPtr)theCell)->next = NULL;
  225.     ((ListHdrPtr)theList)->tail = (ListLinksPtr)theCell;
  226.     
  227.     ++((ListHdrPtr)theList)->nbrOfCells;                                                        /* count cell                    */
  228.     
  229.     return ((void *)theCell);
  230. }
  231.  
  232.  
  233. /*---------------------------------------*
  234.  | cmDeleteListCell - delete a list cell |
  235.  *---------------------------------------*
  236.  
  237.  This function removes the specified cell (theCell) from a list whose header is pointed
  238.  to by theList.  It is up to the caller to free the memory occupied by the cell.  Here
  239.  it is simply "jump out" of the list link structure.  The input cell pointer (theCell) is
  240.  returned as the function result.
  241.  
  242.  If theCell is NULL, nothing is done and NULL is returned.
  243. */
  244.  
  245. void *cmDeleteListCell(const void *theList, const void *theCell)
  246. {
  247.     if (theCell == NULL) return (NULL);                                                        /* safety                             */
  248.     
  249.     if (((ListLinksPtr)theCell)->prev)
  250.         ((ListLinksPtr)theCell)->prev->next = ((ListLinksPtr)theCell)->next;
  251.     else                                                                                                                     /* delete head                     */
  252.         ((ListHdrPtr)theList)->head = ((ListLinksPtr)theCell)->next;
  253.     
  254.     if (((ListLinksPtr)theCell)->next)
  255.         ((ListLinksPtr)theCell)->next->prev = ((ListLinksPtr)theCell)->prev;
  256.     else                                                                                                                     /* delete tail                     */
  257.         ((ListHdrPtr)theList)->tail = ((ListLinksPtr)theCell)->prev;
  258.     
  259.     --((ListHdrPtr)theList)->nbrOfCells;                                                    /* decrement count            */
  260.     
  261.     return ((void *)theCell);
  262. }
  263.  
  264.  
  265. #if !LISTMACROS
  266. /*-------------------------------------------------*
  267.  | cmGetNextListCell - get the next cell on a list |
  268.  *-------------------------------------------------*
  269.  
  270.  Given a pointer to a list cell, this function returns the pointer to the next cell on
  271.  the list or NULL if there is no next cell.
  272.  
  273.  NULL is also returned if the input cell pointer is NULL.
  274. */
  275.  
  276. void *cmGetNextListCell(void *currCell)
  277. {
  278.     if (currCell == NULL) return(NULL);                                                        /* safety                             */
  279.     return (((ListLinksPtr)currCell)->next);
  280. }
  281. #endif
  282.  
  283.  
  284. #if !LISTMACROS
  285. /*-----------------------------------------------------*
  286.  | cmGetPrevListCell - get the previous cell on a list |
  287.  *-----------------------------------------------------*
  288.  
  289.  Given a pointer to a list cell, this function returns the pointer to the previous cell
  290.  on the list or NULL if there is no previous cell.
  291.  
  292.  NULL is also returned if the input cell pointer is NULL.
  293. */
  294.  
  295. void *cmGetPrevListCell(void *currCell)
  296. {
  297.     if (currCell == NULL) return(NULL);                                                        /* safety                             */
  298.     return (((ListLinksPtr)currCell)->prev);
  299. }
  300. #endif
  301.  
  302.  
  303. #if !LISTMACROS
  304. /*---------------------------------------------------------*
  305.  | cmCountListCells - return the number of cells in a list |
  306.  *---------------------------------------------------------*
  307.  
  308.  This function can be used to determine the number of cells in a list.  0 is returned if
  309.  the list is currently empty. It is assumed that the list has been previously initialized
  310.  by cmInitList().
  311. */
  312.  
  313. CM_ULONG cmCountListCells(const void *theList)
  314. {
  315.     return (((ListHdrPtr)theList)->nbrOfCells);
  316. }
  317. #endif
  318.  
  319.  
  320. #if !LISTMACROS
  321. /*----------------------------------------------*
  322.  | cmIsEmptyList - determine if a list is empty |
  323.  *----------------------------------------------*
  324.  
  325.  This function returns true if the specified list is empty (i.e., contains no cells) and
  326.  false otherwise (i.e., contains cells).
  327. */
  328.  
  329. CMBoolean cmIsEmptyList(const void *theList)
  330. {
  331.     return (((ListHdrPtr)theList)->nbrOfCells == 0);
  332. }
  333. #endif
  334.  
  335.  
  336. #if !LISTMACROS
  337. /*----------------------------------------------------------*
  338.  | cmGetListhead - return the pointer to the head of a list |
  339.  *----------------------------------------------------------*/
  340.  
  341. void *cmGetListHead(const void *theList)
  342. {
  343.     return (((ListHdrPtr)theList)->head);
  344. }
  345. #endif
  346.  
  347.  
  348. #if !LISTMACROS
  349. /*----------------------------------------------------------*
  350.  | cmGetListTail - return the pointer to the tail of a list |
  351.  *----------------------------------------------------------*/
  352.  
  353. void *cmGetListTail(const void *theList)
  354. {
  355.     return (((ListHdrPtr)theList)->tail);
  356. }
  357. #endif
  358.  
  359.  
  360. #if !LISTMACROS
  361. /*----------------------------------------------------------*
  362.  | cmNullListLinks - force the links in a list cell to NULL |
  363.  *----------------------------------------------------------*
  364.  
  365.  This is generally done as a safety measure after a cell is allocated.  If the cell finds
  366.  its way into a linked list then most list walkers will be happy with NULL list links if
  367.  they see them.  "Bad" cells like these could arise from error conditions which may be
  368.  seen during a cleanup.
  369. */
  370.  
  371. void *cmNullListLinks(void *theCell)
  372. {
  373.     if (currCell == NULL) return(NULL);                                                        /* safety                             */
  374.     ((ListLinksPtr)theCell)->prev = ((ListLinksPtr)theCell)->next = NULL;
  375.     return (theCell);
  376. }
  377. #endif
  378.  
  379.  
  380. /*------------------------------------------------*
  381.  | cmGetNthListCell - get the N'th cell on a list |
  382.  *------------------------------------------------*
  383.  
  384.  This function returns a pointer to the N'th cell (counting from 1) on a list whose
  385.  header is pointed to by theList.  NULL is returned if there is no N'th list item.
  386. */
  387.  
  388. void *cmGetNthListCell(const void *theList, const CM_ULONG n)
  389. {
  390.     CM_ULONG            i;
  391.     ListLinksPtr     p;
  392.     
  393.     if (n == 0 || n > ((ListHdrPtr)theList)->nbrOfCells)                 /* must have valid "n"        */
  394.         return (NULL);
  395.     
  396.     p = (ListLinksPtr)((ListHdrPtr)theList)->head;                            /* hunt n'th cell down        */
  397.     for (i = 2; i <= n && p; ++i) p = p->next;
  398.     return (p);
  399. }
  400.  
  401.  
  402. /*-------------------------------------------------------------------------------*
  403.  | cmInsertBeforeNthListCell - insert a list cell BEFORE the N'th cell on a list |
  404.  *-------------------------------------------------------------------------------*
  405.  
  406.  This function inserts the specified cell (theCell) before the N'th cell (counting from
  407.  1) on the list whose header is pointed to by theList.  The function returns the input
  408.  inserted cell pointer as its result.
  409.  
  410.  Nothing is inserted and NULL is returned if if there is no N'th list item or theCell is
  411.  NULL.
  412. */
  413.  
  414. void *cmInsertBeforeNthListCell(const void *theList, const void *theCell, const CM_ULONG n)
  415. {
  416.     void *beforeThisCell;
  417.     
  418.     beforeThisCell = cmGetNthListCell(theList, n);                            /*  find n'th cell                */
  419.     if (beforeThisCell == NULL) return (NULL);                                    /* return NULL if no n'th    */
  420.     
  421.     return (cmInsertBeforeListCell(theList, theCell, beforeThisCell)); /* insert cell            */
  422. }
  423.  
  424.  
  425. /*-----------------------------------------------------------------------------*
  426.  | cmInsertAfterNthListCell - insert a list cell AFTER the N'th cell on a list |
  427.  *-----------------------------------------------------------------------------*
  428.  
  429.  This function inserts the specified cell (theCell) after the N'th cell (counting from
  430.  1) on the list whose header is pointed to by theList.  The function returns the input
  431.  inserted cell pointer as its result.
  432.  
  433.  Nothing is inserted and NULL is returned if if there is no N'th list item or theCell is
  434.  NULL.
  435. */
  436.  
  437. void *cmInsertAfterNthListCell(const void *theList, const void *theCell, const CM_ULONG n)
  438. {
  439.     void *afterThisCell;
  440.     
  441.     afterThisCell = cmGetNthListCell(theList, n);                                /* find n'th cell                    */
  442.     if (afterThisCell == NULL) return (NULL);                                        /* return NULL if no n'th    */
  443.  
  444.     return (cmInsertAfterListCell(theList, theCell, afterThisCell));    /* insert cell            */
  445. }
  446.  
  447.  
  448. /*---------------------------------------------------------------------------*
  449.  | cmInsertNthListCell - insert a list cell into the N'th position on a list |
  450.  *---------------------------------------------------------------------------*
  451.  
  452.  This function makes the specified cell (theCell) the N'th cell (counting from 1) on the
  453.  list whose header is pointed to by theList.  The function returns the input inserted
  454.  cell pointer as its result.
  455.  
  456.  Nothing is inserted and NULL is returned or if N is specified as 0 or 1 greater than
  457.  the total number of cells currently on the list.  NULL is also returned if theCell is
  458.  NULL.
  459.  
  460.  If N is specified a 1 greater than the total number of cells currently on the list then
  461.  the new cell is APPENDED to the end of the list.  If N is anything less, the new cell
  462.  is inserted BEFORE the old N'th cell.  Thus the new cell becomes the N'th cell.
  463. */
  464.  
  465. void *cmInsertNthListCell(const void *theList, const void *theCell, const CM_ULONG n)
  466. {
  467.     if (n == 0 || n > ((ListHdrPtr)theList)->nbrOfCells + 1)        /* must have valid "n"        */
  468.         return (NULL);
  469.     
  470.     if (n == ((ListHdrPtr)theList)->nbrOfCells + 1)                            /* if we're appending...    */
  471.         return (cmAppendListCell(theList, theCell));                            /* ...do it and exit            */
  472.     
  473.     return (cmInsertBeforeNthListCell(theList, theCell, n));        /* insert new N'th cell        */
  474. }
  475.  
  476.  
  477. /*-------------------------------------------------------------*
  478.  | cmGetCellPosition - find the position of a cell in its list |
  479.  *-------------------------------------------------------------*
  480.  
  481.  This function returns the position index, 1 to N, of the cell (theCell) in the list whose
  482.  header is pointed to by theList.  The function returns 0 if theCell cannot be found in 
  483.  theList.
  484. */
  485.  
  486. CM_ULONG cmGetCellPosition(const void *theList, const void *theCell)
  487. {
  488.     CM_ULONG          i = 0;
  489.     ListLinksPtr  p = (ListLinksPtr)((ListHdrPtr)theList)->head;
  490.  
  491.     while (p) {                                                                                                    /* loop through all cells    */
  492.         ++i;                                                                                                            /* count the cell                    */
  493.         if (p == (ListLinksPtr)theCell) return (i);                                /* return count if found    */
  494.         p = p->next;                                                                                            /* keep looking                        */
  495.     }
  496.     
  497.     return (0);                                                                                                    /* didn't find it                    */
  498. }
  499.  
  500.  
  501. /*------------------------------------------------------*
  502.  | cmForEachListCell - do some action on each list cell |
  503.  *------------------------------------------------------*
  504.  
  505.  Do (call) the specified action for each cell on the specified list whose header is 
  506.  pointed to by theList. This routine calls (*action)() on each cell along with a "refCon"
  507.  which the caller can use as a communication facility to convey additional info to the
  508.  action routine.  The pointer to the cell is passed to the action routine.
  509. */
  510.  
  511. void cmForEachListCell(const void *theList, CMRefCon refCon,
  512.                                               void (*action)(void *cell, CMRefCon refCon))
  513. {
  514.     ListLinksPtr next, p = (ListLinksPtr)((ListHdrPtr)theList)->head;
  515.     
  516.     while (p) {                                                                                                    /* loop through all cells    */
  517.         next = p->next;                                                                                        /* cell could be deleted    */
  518.         (*action)(p, refCon);
  519.         p = next;
  520.     }
  521. }
  522.  
  523.  
  524. /*-------------------------------------------------------*
  525.  | cmFreeAllListCells - remove all the cells from a list |
  526.  *-------------------------------------------------------*
  527.  
  528.  This routine removes (i.e., free()s) all the cells from the specified list.  The list
  529.  header is reinitialized.  Because it uses the memory deallocator it need the global data
  530.  session pointer.
  531. */
  532.  
  533. void cmFreeAllListCells(const void *theList, SessionGlobalDataPtr sessionData)
  534. {
  535.     ListLinksPtr next, p = (ListLinksPtr)((ListHdrPtr)theList)->head;
  536.     
  537.     while (p) {                                                                                                    /* loop through all cells    */
  538.         next = p->next;                                                                                        /* cell is being deleted    */
  539.         SessionFree(p);
  540.         p = next;
  541.     }
  542.     
  543.     cmInitList(theList);
  544. }
  545.                                                           
  546.                                                             CM_END_CFUNCTIONS
  547.